package SwordForOffer.Problem6;

import SwordForOffer.utils.BinaryTreeNode;

import java.util.Arrays;

/**
 * 利用二叉树性质：中序遍历子树的元素总是在数的一边，前序遍历的树（或子树）根总是在遍历结果的第一个。
 *
 */

public class ConstructBinaryTree {
    public BinaryTreeNode construct(int[] pre, int[] in) {
        boolean isHave = false;
        if (pre == null || in == null){
            return null;
        }
        if (pre.length != in.length){
            return null;
        }

        BinaryTreeNode root = new BinaryTreeNode();
        for(int i = 0; i < in.length ; i++){
            if(pre[0] == in[i]){
                isHave = true;
                root.value = pre[0];
                root.leftNode = construct(Arrays.copyOfRange(pre,1,i + 1)
                        ,Arrays.copyOfRange(in,0,i));
                root.rightNode = construct(Arrays.copyOfRange(pre,i+1,pre.length)
                        ,Arrays.copyOfRange(in,i+1,in.length));
            }

        }
        if(isHave){
            System.out.println(root.value);
        }

        return root;
    }
}
